Doubly Linked List: Each node connects to both Next and Prev.

Doubly Linked List

Двусвязный список расширяет возможности обычного списка, добавляя обратную связь.

  • Prev & Next: Каждый узел хранит два адреса.
  • Бинарная связь: Позволяет удалять элементы с конца за $O(1)$ при наличии указателя на Tail.
  • Memory: Требует больше памяти (дополнительный указатель на каждый узел).
struct Node {
    int data;
    Node* next;
    Node* prev; // Обратная связь
    
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

class DoublyLinkedList {
    Node* head = nullptr;
    Node* tail = nullptr;
    // ... методы push/pop
};